package Hot100;

import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2022-01-14 11:11
 */
public class findTargetSumWays494 {
    /**
     * 494. 目标和
     * 给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
     * 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
     * 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
     * 1、回溯
     * 2、dp，子集划分问题--背包
     * */
    int pathNum;
    void backtrack(int[] nums,int index,int target){
        if (index==nums.length){
            if (target==0)
                pathNum++;
            return;
        }
        if (index>=nums.length) return;
        //作出选择
        backtrack(nums,index+1,target-nums[index]);
        backtrack(nums,index+1,target+nums[index]);
    }
    public int findTargetSumWays1(int[] nums, int target) {
        pathNum=0;
        if (nums.length==0) return 0;
        backtrack(nums,0,target);
        return pathNum;
    }

    //2、将元素分为加号和减号的两堆，推导出寻找nums中存在几个子集，和为（target+sum（nums））/2
    //背包问题，背包容量为sum。dp[i][j]表示在前i个物品中和j最多有几种装法
    int subsets(int[] nums,int sum){
        int n=nums.length;
        int[][] dp=new int[n+1][sum+1];
        for (int i = 0; i <=n ; i++) {
            dp[i][0]=1;
        }
        for (int i = 1; i <=n ; i++) {
            for (int j = 0; j <=sum ; j++) {
                if (j<nums[i-1]){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][sum];
    }
    public int findTargetSumWays(int[] nums, int target) {
        if (nums.length==0) return 0;
        int sum=Arrays.stream(nums).sum();
        if (sum<target||(target+sum)%2==1||-sum>target){
            return 0;
        }
        return subsets(nums,(target+sum)/2);
    }
}
